The present invention relates to image generation, in general, and in particular to image generation from moving camera positions within a geometric model space.
An animated video presentation or display for an interactive game or tool can be provided by a computer, computer system or device capable of computing (“a computing device” as used herein) that has memory for storing parameters of a geometric model space and descriptions of a set of virtual objects (shapes, textures, alpha, location in the model space, etc.) where the computing device considers the space, the objects as well as a camera view point, view direction and view range (e.g., a viewing rectangle or other 2D shape) and from that data, generates a view that shows the virtual objects in their place. It is well known how to render images, or sequences of images such as a video sequence, given that data. There is considerable literature on how to describe the virtual objects such that the rendered views present realistic and/or interesting imagery. For moving image sequences, the camera placement and view are also important.
In an animated feature, it might be desired to maintain visibility of one or more objects and/or points or locations in the model space. For example, where the image sequence is to be presented as a story, it might be desired to keep the main character of the current scene in view as the camera moves to follow that character's movements, or to change the angle of the camera. For video games, where some actions are controlled by a player of the video game and that player controls a virtual character, it might be desired to keep that character in view as the camera view point shifts to take into account player movements of the virtual character. In many video games, where the player can control character movements freely and in real-time, expecting a real-time response from a display, camera movements need to be determined in real-time.
Positioning of a camera in a virtual space is a virtual operation itself. In other words, an actual camera is not placed anywhere, but the computing device computes the image that would result if the virtual objects were real, were placed in space in accordance with the locations indicated by the data representing those virtual objects, and an image captured by a camera located in the corresponding camera location.
Camera control processes for computer graphics are known. A number of examples are shown in [Christie]. Many classical third-person camera models examine the local vicinity in order to resolve occlusions. A common camera model used in computer games casts a ray from the player's character to the current camera view point and “teleports” the camera to the closest intersection, leading to a noticeable jump in view. An alternate scheme makes occluding geometry transparent, which avoids camera jumps but detracts from the environment's realism.
[Halper] presents a more sophisticated local camera model that resolves occlusions using point-based visibility. While that may handle some situations well, its local nature leads to inherent limitations. The camera may not adequately follow a fast moving character or resolve a complicated visibility situation, resulting in discontinuous jumps or passing through scene geometry. It is often preferable to have a global process that handles large-scale camera transitions and can “follow” an avatar, character or other object in a natural fashion without discontinuous jumps or collisions with objects in the scene.
Some high-level approaches to camera control focus on virtual cinematography, in which cinematographic knowledge is incorporated into the choice of camera position and scene composition. For example, [Bares] describes a constraint-based camera planner for shot composition that models different cinematic styles, and [He] describes encoding film-making heuristics into a hierarchical finite state machine that controls camera selection and placement. Cinematographic rules may provide a sequence of shot placements and focus targets, but often do not directly handle the actual camera motion between such shots. [Drucker] presents an alternative for advanced camera control with visibility-based path optimization.
As shown by surveys on the topic ([Cohen-Or], [Bittner], [Durand]), many visibility algorithms strive to identify which objects, lights, or other portions of a scene are visible from a given vantage. Runtime visibility calculations can be accelerated via precomputation, in which a visibility relationship between “viewcells” in space and scene objects is established. The problem of visibility transition planning, such as defining a path, is closely related to the topic of motion planning in the robotics literature where optimal paths are found for robot navigation, as mentioned by [LaValle] and [Masehian]. Many motion planning algorithms employ a roadmap construction in which the free and uncolliding configuration space of a robot is mapped to a graph data structure, reducing the planning problem to a graph search. [LaValle] describes this approach.
Some processes for motion planning incorporate a notion of visibility into the graph reduction in the form of a sparse set of guard nodes whose visibility region can be defined by unobstructed straight lines in configuration space, as described in [Varadhan], or by the ability of a local planner to navigate without intersection, as described in [Simeon]. The related problem of target tracking strives to compute the motion of a robot observer in order to maintain visibility of a moving target. Sophisticated algorithms address this problem in planar environments with polygonal obstacles and are described by [Murrieta-Cid2004], [Bandyopadhyay2004], [Bandyopadhyay2006]. However, direct extension of this work to full 3D motion is non-trivial, partly because visibility relationships are significantly more complex, as explained by the 3D target tracking approach of [Bandyopadhyay2007], which presents an online algorithm designed for an unknown environment where input comes from a robot's visual sensors. In virtual environments, the entire scene is usually known a priori and the camera should make use of this information to find more natural transitions. Other work on 3D tracking does not deal with occlusions ([Vidal]) or presents interesting theoretical results without demonstrating a system that matches the strict efficiency demands of animation and/or games ([Murrieta-Cid2007], [Lazebnik]).
[Salomon] describes an approach wherein a roadmap is created in which nodes represent an avatar's position and edges connect nodes between which a local planner can successfully navigate. [Niederberger] presents a navigation system using a shortest-path search on a triangulated height-field terrain. Often, these approaches do not meet the needs of particular systems, such as where cameras might not be tied to walkable surfaces, but available in the full ambient space, or where dense visibility needs to be considered.
For these and other reasons, improved camera path planning is needed for some applications.